package io.github.maojian.dynamicprogramming;

import org.junit.Test;

/**
 * @Auther: jian.mao
 * @Date: 2022-06-22 13:58
 * @Description: https://leetcode.cn/problems/min-cost-climbing-stairs/
 */
public class Q746 {
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        int[] dp = new int[length + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[length];
    }

    public int minCostClimbingStairs01(int[] cost) {
        int length = cost.length;
        int first = 0, second = 0, temp;
        for (int i = 2; i <= length; i++) {
            temp = Math.min(first + cost[i-2],second+cost[i-1]);
            first = second;
            second = temp;
        }
        return second;
    }

    @Test
    public void test() {
        int[] cost = new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println(minCostClimbingStairs01(cost));
    }
}
